FIG. 1 depicts a conventional computer system 10. The computer system 10 has a processor 12, a main memory 14, a disk memory 16 and an input device 18, such as a keyboard and mouse. The devices 12-18 are connected to a bus 20 which transfers data, i.e., instructions and information, between each of these devices 12-18. A graphics controller 30 is also connected to the bus 20. As shown, the graphics controller 30 includes a drawing processor 32. The drawing processor is also connected to an address generator 36 and a data input of a frame buffer 34. The address generator 36, in turn, is connected to RAS (row address select), CAS (column address select) and chip select inputs of the frame buffer 34. Illustratively, the frame buffer 34 is implemented with plural VRAMs (video random access memories) or DRAMs (dynamic random access memories). The frame buffer 34 is connected to a display device 38, such as a cathode ray tube (CRT) or liquid crystal display (LCD) monitor.
The drawing processor 32 receives instructions from the processor 12 for drawing objects. For instance, in the case of a computer aided design (CAD) application, the processor 12 may receive user input regarding creating and locating objects in 3-D space. The processor 12, in turn, transfers instructions regarding the size, location, texture, translucence, etc. of such objects to the drawing processor 32. In response, the drawing processor 32 creates a pixel image representation of a plane of view of such objects in 3-D space. The pixels of the image of each plane of view form part of a frame that is stored by the drawing processor 32 in the frame buffer 34. Several drawing processors 32 are known, such as is disclosed in U.S. Pat. Nos. 5,046,023 and 5,185,856. The latter reference discloses a drawing processor that is specifically adapted for rendering 3-D objects.
A computer system 10 capable of performing 3-D rendering advantageously "maps" texture onto the rendered object. The mapping of texture onto objects is well known and is not discussed in detail herein. See U.S. Pat. No. 5,222,205; L. Williams, Pyramidal Parametrics, ACM COMPUTER GRAPHICS, vol. 17, no.3 p.1-11 (1983); and W. NEWMAN & R. SPROULL, PRINCIPLES OF INTERACTIVE COMPUTER GRAPHICS, 2d ed., p. 389-410. Suffice it to say that the texture pattern may be considered a renderable source texture surface which is to be mapped onto a destination object surface. The object thus formed may then be mapped onto the destination plane of view.
Such mapping is very computation intensive. As noted in the above-noted Williams article, such mapping may require sampling the texture data in a fashion which is suited to the view of the surface of the destination object. That is, the visibility of the texture detail on the object surface depends on how close or how far the object surface is located in 3-D space from the plane of view. As the plane of view is brought closer to the object surface, more texture detail is visible. As the plane of view is move away from the object surface, less texture detail is visible.
To reduce the amount of computation involved in mapping texture when the object is moved closer or farther from the plain of view, the Williams article proposes to initially provide subsamplings of the textured data. This is illustrated in FIG. 2. As shown, the texture data is stored in 2-D data arrays. The texture data in each array is indexed, i.e., addressed with 2-D virtual address coordinates (u,v), i.e., one in each direction U and V. The texture data consists of RGB data including one fixed length data unit (e.g., byte) for each color red (R), green (G) and blue (B) per point of texture data. The R data is stored in array 61, the G data is stored in array 62 and the B data is stored in array 63. As per the Williams memory storage scheme, the array 64 is used for storing subsampled versions of the RGB data. For instance, subarray 71 of array 64 stores a 1/2 subsampling in both the U and V directions of the R data of array 61. Likewise, subarray 72 stores a 1/2 subsampling in both the U and V directions of the G data of array 62. Subarray 73 stores a 1/2 subsampling in both the U and V directions of the B data of array 63. The subsampling process is then carried out again in subarray 74 which has subarrays 81, 82 and 83 which contain 1/4 subsamplings in both the U and V directions of the R,G, and B data of arrays 61, 62 and 63, respectively. Likewise, subarrays 91, 92 and 93 of subarray 84 contain 1/8 subsamplings in both the U and V directions of the R,G and B data arrays 61, 62 and 63, respectively. This subsampling is carried out until one texture data per color is obtained. This data structure 51 is referred to as a "mip map." In a mip map 51, the full scale RGB data (in arrays 61, 62 and 63) is said to be subsampled at level d=0, the 1/2 subsampled RGB data (in arrays 71, 72 and 73) is said to be subsampled at level d=1, and so on. In general, the 2.sup.-d subsampled data is said to be subsampled at level d.
In order to map texture data onto an object, the appropriate level RGB texture data array is used. Alternatively, if the object surface size is between two arrays that are subsampled at levels d and d+1, a bilinear interpolation between the texture data of the two data arrays is used. The mip map scheme therefore provides a relatively low computation manner of mapping texture onto an arbitrary sized object surface.
Consider now the case where the object is both displaced away from, and rotated with respect to, the plane of view. The mip map can still be used to map texture on to the object surface. However, because the object surface has rotated, the interpolated texture values produced using the mip map may produce aliasing or blurring artifacts in the image. To remedy this problem, U.S. Pat. No. 5,222,205 proposes a modified data structure referred to as a "rip map." A rip map 52 is illustrated in FIG. 3. Illustratively, the rip map 52 shown in FIG. 3 is for the R texture data. Therefore, a rip map for the G and B data would also be provided.
The rip map 52 has a full scale data array 61' including one R value for each pixel of the object surface. Like the mip map 51, the rip map 52 also includes plural subsampled versions of the full scale data array 61'. However, the subsampled arrays of the rip map 52 need not be sampled in each direction U and V the same. For instance, data array 62' is 1/2 subsampled only in the direction U. Data array 63' is 1/4 subsampled only in the direction U. Data array 64' is 1/8 subsampled only in the direction U, and so on. Likewise, data array 65' is 1/2 subsampled only in the direction V, data array 66' is 1/4 subsampled only in the direction V and data array 67' is 1/8 subsampled only in the direction V. The rip map contains other permutations of subsampling, such as data array 75' which is 1/2 subsampled in the direction U and 1/8 subsampled in the direction V. Two levels of subsampling (du,dv) are therefore used to designate a specific data array. The following table summarizes the assignment of levels to the subsampled data arrays:
TABLE 1 ______________________________________ Label du dv u dir. sampl. v dir. sampl. ______________________________________ 61' 0 0 1 1 62' 1 0 1/2 1 63' 2 0 1/4 1 64' 3 0 1/8 1 65' 0 1 1 1/2 66' 0 2 1 1/4 67' 0 3 1 1/8 71' 1 1 1/2 1/2 72' 2 1 1/4 1/2 73' 3 1 1/8 1/2 74' 1 2 1/2 1/4 75' 1 3 1/2 1/8 81' 2 2 1/4 1/4 82' 3 2 1/8 1/4 83' 2 3 1/4 1/8 91' 3 3 1/8 1/8 du dv 2.sup.-du 2.sup.-dv ______________________________________
The rip map 51 provides more choices in subsampled data for use in the interpolation. This tends to reduce the aforementioned aliasing and blurring artifacts.
Desirably, RGB texture data is supplemented with alpha data A to form RGBA data for each pixel. The A data may indicate, for instance, the property of "translucence" or the amount of incident light that can pass through the object. For instance, suppose an object models a green lens which passes 80% of the light incident thereon. If such a lens is placed in front of other objects in the background with respect to the plane of view, then the occluded pixels of the objects should have a blended color. In particular, the occluded object pixels should have a color which is 80% of their original color and 20% of the color of the green lens.
Both mip maps and rip maps are useful in reducing the amount of computation for mapping texture data onto an object surface. However, the mip map can only accommodate three data values per pixel, namely, RGB. Alpha data cannot be accommodated in the mip map shown in FIG. 2. In addition, both the mip map and rip map are implemented using 2-D virtual coordinate addresses. However, if such 2-D addresses are used to organize the physical storage of the texture data in the VRAMs/DRAMs of the frame buffer, then much of the storage capacity of the VRAMs/DRAMs tends to be wasted. This is illustrated in FIG. 4. As shown in FIG. 4, the two dimensions of the texture data rarely conform to the dimensions of the memory array of the VRAMs/DRAMs. For instance, the suppose texture data has the same dimensions of a display frame, such as 900.times.1152. Two banks of four VRAMs/DRAMs each are used to store the texture data in an interleaved fashion. Nevertheless, the shaded areas of the VRAMs/DRAMs are wasted. See U.S. Pat. Nos. 5,321,425, 5,268,682, and 5,268,681.
It is therefore an object of the present invention to overcome the disadvantages of the prior art.